import javax.swing.tree.TreeNode;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 石方旭
 * Date: 2022-05-01
 * Time: 19:37
 */
//最大差值
class Solution1 {
    public int maximumDifference(int[] nums) {
        //暴力求解
        int max =-1;
        for(int i =0;i<nums.length;++i) {
            for(int j = i+1;j<nums.length;++j) {
                if(nums[i]<nums[j]&&nums[j]-nums[i]>max) {
                    max = nums[j] - nums[i];
                }
            }
        }
        return max;
    }
}

//
//class Solution {
//    int INF = 0x3f3f3f3f;
//    public List<Integer> getAllElements(TreeNode root1, TreeNode root2) {
//        List<Integer> ans = new ArrayList<>();
//        List<Integer> l1 = new ArrayList<>(), l2 = new ArrayList<>();
//        dfs(root1, l1); dfs(root2, l2);
//        int n = l1.size(), m = l2.size(), i = 0, j = 0;
//        while (i < n || j < m) {
//            int a = i < n ? l1.get(i) : INF, b = j < m ? l2.get(j) : INF;
//            if (a <= b) {
//                ans.add(a); i++;
//            } else {
//                ans.add(b); j++;
//            }
//        }
//        return ans;
//    }
//    void dfs(TreeNode root, List<Integer> list) {
//        if (root == null) return ;
//        dfs(root.left, list);
//        list.add(root.val);
//        dfs(root.right, list);
//    }
//}

class Solution3 {
    public int[] sortArrayByParityII(int[] nums) {
        //这个题不就是偶数排到数组的前面 奇数排到数组的后面么
        int left =0;
        int right = nums.length-1;
        while(left<right) {
            //左边找偶数位置上的奇数
            while(left<right && nums[left]%2==0&&left%2==1){
                left++;
            }
            //右边找奇数位置上的偶数
            while(left<right&&nums[right]%2==1&&right%2==0){
                right--;
            }
            //奇数偶数进行交换
            int tmp =nums[left];
            nums[left]= nums[right];
            nums[right] =tmp;
        }
        return nums;
    }
}

class Solution {
    public int[] sortArrayByParityII(int[] nums) {
        int n = nums.length;
        int j = 1;
        for (int i = 0; i < n; i += 2) {
            if (nums[i] % 2 == 1) {
                while (nums[j] % 2 == 1) {
                    j += 2;
                }
                swap(nums, i, j);
            }
        }
        return nums;
    }

    public void swap(int[] nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
}

public class LeetCode {

    public static void main(String[] args) {
        Solution solution = new Solution();
        int[] array = {4,2,5,7};
        solution.sortArrayByParityII(array);
        System.out.println(Arrays.toString(solution.sortArrayByParityII(array)));
    }
}
